# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        # b = []
        # a = []
        # a.append((root ,0))
        # while a:
        #     node,level = a.pop(0)
        #     if node :
        #         if len(b) < level +1:
        #             b.insert(level+1,[])
        #         b[level].append(node.val)
        #         a.append((node.left, level + 1))
        #         a.append((node.right, level + 1))
        # for i in range(len(b)):
        #     s = 0
        #     count = 0
        #     for j in b[i]:
        #         s += j
        #         count += 1
        #     m = s / count
        #     b[i] = m
        # return b

        b = []
        a = []
        a.append((root ,0))
        while a:
            node,level = a.pop(0)
            if node :
                if len(b) < level +1:
                    b.insert(level+1,[])
                b[level].append(node.val)
                a.append((node.left, level + 1))
                a.append((node.right, level + 1))

        return [sum(b[i])/len(b[i]) for i in range(len(b))]













m1 = TreeNode(3)
m1.left = TreeNode(9)
m1.right = TreeNode(20)
m1.right.right = TreeNode(7)
m1.right.left= TreeNode(15)
# m1.right.right.right = TreeNode(3)
# m1.right.right.right.right= TreeNode(3)

s = Solution()

t = s.averageOfLevels(m1)
print(t)
